{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Longest Awesome Substring"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #hash-table #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #哈希表 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: longestAwesome"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找出最长的超赞子字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串 <code>s</code> 。请返回 <code>s</code> 中最长的 <strong>超赞子字符串</strong> 的长度。</p>\n",
    "\n",
    "<p>「超赞子字符串」需满足满足下述两个条件：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>该字符串是 <code>s</code> 的一个非空子字符串</li>\n",
    "\t<li>进行任意次数的字符交换后，该字符串可以变成一个回文字符串</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;3242415&quot;\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>&quot;24241&quot; 是最长的超赞子字符串，交换其中的字符后，可以得到回文 &quot;24142&quot;\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;12345678&quot;\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;213123&quot;\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>&quot;213123&quot; 是最长的超赞子字符串，交换其中的字符后，可以得到回文 &quot;231132&quot;\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;00&quot;\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10^5</code></li>\n",
    "\t<li><code>s</code> 仅由数字组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-longest-awesome-substring](https://leetcode.cn/problems/find-longest-awesome-substring/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-longest-awesome-substring](https://leetcode.cn/problems/find-longest-awesome-substring/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"3242415\"', '\"12345678\"', '\"213123\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestAwesome(self, s: str) -> int:\n",
    "        \n",
    "        n = len(s)\n",
    "        pre = dict()\n",
    "        pre[0] = -1\n",
    "        x = 0\n",
    "        ans = 0\n",
    "        for i, w in enumerate(s):\n",
    "            x ^= (1<<int(w))\n",
    "            if x in pre and i-pre[x] > ans:\n",
    "                ans = i-pre[x]\n",
    "            for j in range(10):\n",
    "                y = x^(1<<j)\n",
    "                if y in pre and i-pre[y] > ans:\n",
    "                    ans = i-pre[y]\n",
    "            if x not in pre:\n",
    "                pre[x] = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestAwesome(self, s: str) -> int:\n",
    "        res = 0\n",
    "        status = 0\n",
    "        pos = {}\n",
    "        pos[0] = -1\n",
    "        for i in range(len(s)):\n",
    "            char = ord(s[i]) - ord('0')\n",
    "            status ^= 1<<char\n",
    "            if status in pos.keys():\n",
    "                res = max(res, i - pos[status])\n",
    "            else:\n",
    "                pos[status] = i\n",
    "            for j in range(10):\n",
    "                mask_pre = status ^ (1<<j)\n",
    "                if mask_pre in pos.keys():\n",
    "                    res = max(res, i - pos[mask_pre])\n",
    "            \n",
    "        return res        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestAwesome(self, s: str) -> int:\n",
    "        ans = cur = 0\n",
    "        pre = {0:-1}\n",
    "        for i, j in enumerate(map(int, s)):\n",
    "            cur ^= 1 << j\n",
    "            for k in range(10):\n",
    "                maybe = cur ^ 1 << k\n",
    "                if maybe in pre:\n",
    "                    ans = max(ans, i - pre[maybe])\n",
    "            if cur not in pre: pre[cur] = i\n",
    "            else: ans = max(ans, i - pre[cur])\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestAwesome(self, s: str) -> int:\n",
    "        ans = cur = 0\n",
    "        pre = {0:-1}\n",
    "        for i, j in enumerate(map(int, s)):\n",
    "            cur ^= 1 << j\n",
    "            ans = max([i - pre[maybe] for k in range(11) if (maybe:=(cur ^ 1 << k) & 1023) in pre] + [ans])\n",
    "            if cur not in pre: pre[cur] = i\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestAwesome(self, s: str) -> int:\n",
    "        st, ans = 0, 1\n",
    "        pre = {}\n",
    "        pre[st] = -1\n",
    "        for i, x in enumerate(s):\n",
    "            x = int(x)\n",
    "            st ^= 1 << x\n",
    "            if st in pre:\n",
    "                ans = max(ans, i - pre[st])\n",
    "            for j in range(10):\n",
    "                cur = st ^ (1 << j)\n",
    "                if cur in pre:\n",
    "                    ans = max(ans, i - pre[cur])\n",
    "            if st not in pre:\n",
    "                pre[st] = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestAwesome(self, s: str) -> int:\n",
    "        res = mask = 0\n",
    "        cnt = Counter({0:-1})\n",
    "        for i, ch in enumerate(s):\n",
    "            mask ^= 1<<int(ch)\n",
    "            if mask not in cnt:\n",
    "                cnt[mask] = i            \n",
    "            res = max(res, i - cnt[mask])\n",
    "            for j in range(10):\n",
    "                m = mask ^ (1 << j)\n",
    "                if m in cnt:\n",
    "                    res = max(res, i - cnt[m])\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestAwesome(self, s: str) -> int:\n",
    "        ans = cur = 0\n",
    "        pre = {0:-1}\n",
    "        for i, j in enumerate(map(int, s)):\n",
    "            cur ^= 1 << j\n",
    "            for k in range(10):\n",
    "                maybe = cur ^ 1 << k\n",
    "                if maybe in pre:\n",
    "                    ans = max(ans, i - pre[maybe])\n",
    "                    \n",
    "            if cur not in pre: pre[cur] = i\n",
    "            else: ans = max(ans, i - pre[cur])\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestAwesome(self, s: str) -> int:\n",
    "        pre = [-inf] * (1 << 10)\n",
    "        l = 0\n",
    "        ans = 0\n",
    "        status = 0\n",
    "        pre[0] = -1\n",
    "        for r in range(len(s)):\n",
    "            status ^= 1 << (int(s[r]))\n",
    "            for i in range(10):\n",
    "                cur = status ^ (1 << i)\n",
    "                if pre[cur] != -inf:\n",
    "                    ans = max(ans, r - pre[cur])\n",
    "            if pre[status] != -inf:\n",
    "                ans = max(ans, r - pre[status])\n",
    "            if pre[status] == -inf:\n",
    "                pre[status] = r\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestAwesome(self, s: str) -> int:\n",
    "        # n = len(s)\n",
    "        # prefix = {0: -1}\n",
    "        # result = 0\n",
    "        # mask = 0\n",
    "\n",
    "        # for i in range(n):\n",
    "        #     digit = int(s[i])\n",
    "        #     mask ^= 1 << digit\n",
    "        #     if mask not in prefix:\n",
    "        #         prefix[mask] = i\n",
    "        #     for j in range(10):\n",
    "        #         new_mask = mask ^ (1 << j)\n",
    "        #         if new_mask in prefix:\n",
    "        #             result = max(result, i - prefix[new_mask])\n",
    "        #     if mask in prefix:\n",
    "        #         result = max(result, i - prefix[mask])\n",
    "        #     else:\n",
    "        #         prefix[mask] = i\n",
    "\n",
    "        # return result\n",
    "        n=len(s)\n",
    "        prefix={0:-1}\n",
    "        result=0\n",
    "        mask=0\n",
    "        for i in range(n):\n",
    "            digit=int(s[i])\n",
    "            mask^=1<<digit\n",
    "            if mask not in prefix:\n",
    "                prefix[mask]=i\n",
    "            for j in range(10):\n",
    "                new_mask=mask^(1<<j)\n",
    "                if new_mask in prefix:\n",
    "                    result=max(result,i-prefix[new_mask])\n",
    "            if mask in prefix:\n",
    "                result=max(result,i-prefix[mask])\n",
    "            else:\n",
    "                prefix[mask]=i\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestAwesome(self, s: str) -> int:\n",
    "        memo, ans = {0:-1}, 0\n",
    "        b = 0\n",
    "        for i in range(len(s)):\n",
    "            b ^= 1 << int(s[i])\n",
    "            if b in memo:\n",
    "                ans = max(ans, i - memo[b])\n",
    "            else:\n",
    "                memo[b] = i\n",
    "            # 一个数字出现奇数次，其余出现偶数次\n",
    "            for j in range(10):\n",
    "                curB = b ^ (1 << j)\n",
    "                if curB in memo:\n",
    "                    ans = max(ans, i - memo[curB])\n",
    "        return ans\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestAwesome(self, s: str) -> int:\n",
    "        ans = mask = 0\n",
    "        cnt = {0:-1}\n",
    "        for i, c in enumerate(s):\n",
    "            mask ^= 1 << (ord(c) - ord('0'))\n",
    "            for j in range(10):\n",
    "                if mask ^ (1 << j) in cnt:\n",
    "                    ans = max(ans, i - cnt[mask ^ (1 << j)])\n",
    "            if mask not in cnt:\n",
    "                cnt[mask] = i\n",
    "            else:\n",
    "                ans = max(ans, i - cnt[mask])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestAwesome(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        mp = defaultdict(int)\n",
    "        mp[0] = -1\n",
    "        cur = 0\n",
    "        ans = 1\n",
    "        for i,c in enumerate(s):\n",
    "            c = int(c)\n",
    "            cur ^= (1<<c)\n",
    "            # print(i,c,bin(cur)[2:])\n",
    "            if cur in mp.keys():\n",
    "                if cur == 0 and i==n-1:\n",
    "                    ans = max(ans,i-mp[cur])\n",
    "                else:\n",
    "                    ans = max(ans,i-mp[cur]+1)\n",
    "            else:\n",
    "                mp[cur] = i\n",
    "            # 判断再带一个的情况\n",
    "    \n",
    "            for j in range(10):\n",
    "                curr = cur ^(1<<j)\n",
    "                if curr in mp.keys():\n",
    "                    ans = max(ans, i-mp[curr])\n",
    "        \n",
    "                \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestAwesome(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        aux = {}\n",
    "        aux[0] = 0\n",
    "        get_n = lambda x: ord(x) - ord('0')\n",
    "        rs = 0\n",
    "        for i, ch in enumerate(s):\n",
    "            rs ^= 1<<get_n(ch)\n",
    "            r  = i+1\n",
    "            if rs in aux:\n",
    "                ans = max(ans,r - aux[rs])\n",
    "            for k in range(10):    \n",
    "                if rs ^ (1<<k) in aux:\n",
    "                    ans = max(ans, r - aux[rs^(1<<k)])\n",
    "                \n",
    "            if rs not in aux:\n",
    "                aux[rs] = r\n",
    "        return ans\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestAwesome(self, s: str) -> int:\n",
    "        pre, res = 0, 0\n",
    "        pos = {0:-1}\n",
    "        for i in range(len(s)):\n",
    "            x = int(s[i]) - 0\n",
    "            pre ^= (1 << x)\n",
    "            if pre in pos:\n",
    "                res = max(res, i - pos[pre])\n",
    "            for j in range(10):\n",
    "                also = pre ^ (1 << j)\n",
    "                if also in pos:\n",
    "                    res = max(res, i - pos[also])\n",
    "            if pre not in pos:\n",
    "                pos[pre] = i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestAwesome(self, s: str) -> int:\n",
    "        get_n = lambda x: ord(x) - ord('0')\n",
    "        rs= ans = 0\n",
    "        aux = {}\n",
    "        aux[0] = 0\n",
    "        for i,ch in enumerate(s):\n",
    "            rs = rs ^(1<<get_n(ch))\n",
    "            if rs in aux:\n",
    "                ans = max(ans, i+1 - aux[rs])\n",
    "            for k in range(10):\n",
    "                cur = rs ^(1<<k)\n",
    "                if cur in aux:\n",
    "                    ans = max(ans, i+1-aux[cur])\n",
    "            if rs not in aux:        \n",
    "                aux[rs] = i+1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestAwesome(self, s: str) -> int:\n",
    "\n",
    "        mask=0\n",
    "        dic={0:-1}\n",
    "        res=1\n",
    "        for i,v in enumerate(s):\n",
    "            mask^=1<<int(v)\n",
    "            if mask in dic:\n",
    "                res=max(res,i-dic[mask])\n",
    "            else:\n",
    "                dic[mask]=i\n",
    "            for j in range(10):\n",
    "                if mask^(1<<j) in dic:\n",
    "                    res=max(res,i-dic[mask^(1<<j)])\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestAwesome(self, s: str) -> int:\n",
    "        # 我的理解：首先，我们可以用状态压缩去存储每个数出现次数的奇偶性，无需统计个数\n",
    "        # 用0-1分别奇偶，用一个数mask作为二进制字符串表示0-9每个数字的出现次数的奇偶性\n",
    "        mask = 0\n",
    "        memo = {0: -1}\n",
    "        # memo当中存储的key指的是一个二进制字符串，对应的value是这个二进制字符串指向的s中的index\n",
    "        # 原理详细来说就是[0:i-1]与[0:j]两个substring对应的二进制字符串在位数上相差0或1\n",
    "        # 即0位不同或是1位不同，才能让substring[i:j]具有超赞子串的性质\n",
    "        # 遍历一遍s，对于每一次加入的新元素，找到以前的相同字符串并计算index差，或是找到字符串位数差1\n",
    "        # 的index，计算差值；\n",
    "        # 最终返回的是最大的index差\n",
    "        max_length = 0\n",
    "        for i in range(len(s)):\n",
    "            # 进行位运算，将mask当中的digit s[i]取反\n",
    "            mask ^= (1 << int(s[i]))\n",
    "            if mask in memo:\n",
    "                max_length = max(max_length, i - memo[mask])\n",
    "            else:\n",
    "                memo[mask] = i\n",
    "            for j in range(10):\n",
    "                if (mask ^ (1 << j)) in memo:\n",
    "                    max_length = max(max_length, i - memo[mask ^ (1 << j)])\n",
    "        return max_length\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestAwesome(self, s: str) -> int:\n",
    "        ans = cur = 0\n",
    "        pre = {0:-1}\n",
    "        for i, j in enumerate(map(int, s)):\n",
    "            cur ^= 1 << j\n",
    "            for k in range(11):\n",
    "                if (maybe:=(cur ^ 1 << k) & 1023) in pre and i - pre[maybe] > ans:\n",
    "                    ans = i - pre[maybe]\n",
    "            if cur not in pre: pre[cur] = i\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def longestAwesome(self, s: str) -> int:\r\n",
    "        res = -1\r\n",
    "        mask = 0\r\n",
    "        preCnt = [-1] * 1024\r\n",
    "        preCnt[0] = 0\r\n",
    "\r\n",
    "        for i, idx in enumerate(map(int, s)):\r\n",
    "            mask ^= 1 << idx\r\n",
    "            if preCnt[mask] > -1:\r\n",
    "                res = max(res, i - preCnt[mask] + 1)\r\n",
    "            else:\r\n",
    "                preCnt[mask] = i + 1\r\n",
    "            for j in range(10):\r\n",
    "                if preCnt[mask ^ (1 << j)] > -1:\r\n",
    "                    res = max(res, i - preCnt[mask ^ (1 << j)] + 1)\r\n",
    "        \r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestAwesome(self, s: str) -> int:\n",
    "        # P[r+1] ^P[l] = cur_sum\n",
    "        # cur_sum.bit_count() <=1\n",
    "        ans = rs = 0\n",
    "        aux = {}\n",
    "        get_n = lambda x : ord(x) - ord('0')\n",
    "        aux[0]= 0\n",
    "        for r,ch in enumerate(s):\n",
    "            rs = rs ^ (1<<get_n(ch))\n",
    "            if rs in aux:\n",
    "                ans = max(ans, r+1-aux[rs])\n",
    "            for i in range(10):\n",
    "                cur = rs ^ (1<<i)\n",
    "                if cur in aux:\n",
    "                    ans = max(ans, r+1-aux[cur])\n",
    "\n",
    "            if rs not in aux:\n",
    "                aux[rs] = r+1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestAwesome(self, s: str) -> int:\n",
    "        ans = cur = 0\n",
    "        pre = {0:-1}\n",
    "        for i, j in enumerate(map(int, s)):\n",
    "            cur ^= 1 << j\n",
    "            ans = max(ans, max(i - pre[maybe] for k in range(11) if (maybe:=(cur ^ 1 << k) & 1023) in pre))\n",
    "            if cur not in pre: pre[cur] = i\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestAwesome(self, s: str) -> int:\n",
    "\n",
    "        cnt = {}\n",
    "        cur = 0\n",
    "        ans = 1\n",
    "        for i, ch in enumerate(s):\n",
    "            cur ^= 1 << int(ch)\n",
    "            if not cur or cur.bit_count() == 1:\n",
    "                ans = i + 1\n",
    "            else:\n",
    "                for j in range(10):\n",
    "                    if cur ^ 1 << j in cnt:\n",
    "                        ans = max(ans, i - cnt[cur ^ 1 << j])\n",
    "            if cur not in cnt:\n",
    "                cnt[cur] = i\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestAwesome(self, s: str) -> int:\n",
    "        current = 0\n",
    "        check = {0: -1}\n",
    "        result = 0\n",
    "        for i in range(len(s)):\n",
    "            current = current ^ (1 << int(s[i]))\n",
    "            if current in check:\n",
    "                result = max(result, i - check[current])\n",
    "            else:\n",
    "                check[current] = i\n",
    "            for j in range(10):\n",
    "                current_diff1 = current ^ (1 << j)\n",
    "                if current_diff1 in check:\n",
    "                    result = max(result, i - check[current_diff1])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestAwesome(self, s: str) -> int:\n",
    "        get_n = lambda x:ord(x) - ord('0')\n",
    "        rs, ans = 0,0\n",
    "        aux = {}\n",
    "        aux[0] = 0\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            ch = s[i]\n",
    "            rs = rs ^ (1<<get_n(ch))\n",
    "            if rs in aux:\n",
    "                ans = max(ans, i+1 - aux[rs])\n",
    "            for k  in range(10):\n",
    "                cur = rs ^ (1<<k)\n",
    "                if cur in aux:\n",
    "                    ans = max(ans, i+1 - aux[cur])\n",
    "            if rs not in aux:\n",
    "                aux[rs] = i+1\n",
    "        return ans\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestAwesome(self, s: str) -> int:\n",
    "        get_n= lambda ch: ord(ch) - ord('0')\n",
    "        aux = {}\n",
    "        aux[0] =  0\n",
    "        n = len(s)\n",
    "        rs = ans = 0\n",
    "        for i in range(n):\n",
    "            ch = s[i]\n",
    "            rs = rs ^ (1<<get_n(ch))\n",
    "            if rs in aux:\n",
    "                ans = max(ans, i+1 -aux[rs])\n",
    "            for k in range(10):\n",
    "                if rs ^ (1<<k) in aux:\n",
    "                    ans = max(ans, i+1-aux[rs^(1<<k)])\n",
    "            if rs not in aux:\n",
    "                aux[rs] = i+1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestAwesome(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        prefix = {0: -1}\n",
    "        result = 0\n",
    "        mask = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            digit = int(s[i])\n",
    "            mask ^= 1 << digit\n",
    "            if mask not in prefix:\n",
    "                prefix[mask] = i\n",
    "            for j in range(10):\n",
    "                new_mask = mask ^ (1 << j)\n",
    "                if new_mask in prefix:\n",
    "                    result = max(result, i - prefix[new_mask])\n",
    "            if mask in prefix:\n",
    "                result = max(result, i - prefix[mask])\n",
    "            else:\n",
    "                prefix[mask] = i\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestAwesome(self, s: str) -> int:\n",
    "        # P[r+1] ^P[l] = cur_sum\n",
    "        # cur_sum.bit_count() <=1\n",
    "        ans = rs = 0\n",
    "        aux = {}\n",
    "        get_n = lambda x : ord(x) - ord('0')\n",
    "        aux[0]= 0\n",
    "        for r,ch in enumerate(s):\n",
    "            rs = rs ^ (1<<get_n(ch))\n",
    "            if rs in aux:\n",
    "                ans = max(ans, r+1-aux[rs])\n",
    "            for i in range(10):\n",
    "                cur = rs ^ (1<<i)\n",
    "                if cur in aux:\n",
    "                    ans = max(ans, r+1-aux[cur])\n",
    "\n",
    "            if rs not in aux:\n",
    "                aux[rs] = r+1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestAwesome(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        prefix={0:-1}\n",
    "        ans,sequence=0,0\n",
    "\n",
    "        for j in range(n):\n",
    "            digit=ord(s[j])-ord('0')\n",
    "            sequence^=(1<<digit)\n",
    "            if sequence in prefix:\n",
    "                ans=max(ans,j-prefix[sequence])\n",
    "            else:\n",
    "                prefix[sequence]=j\n",
    "            for k in range(10):\n",
    "                if sequence^(1<<k) in prefix:\n",
    "                    ans=max(ans,j-prefix[sequence^(1<<k)])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestAwesome(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        prefix = {0: -1}\n",
    "        ans, sequence = 0, 0\n",
    "\n",
    "        for j in range(n):\n",
    "            digit = ord(s[j]) - ord(\"0\")\n",
    "            sequence ^= (1 << digit)\n",
    "            if sequence in prefix:\n",
    "                ans = max(ans, j - prefix[sequence])\n",
    "            else:\n",
    "                prefix[sequence] = j\n",
    "            for k in range(10):\n",
    "                if sequence ^ (1 << k) in prefix:\n",
    "                    ans = max(ans, j - prefix[sequence ^ (1 << k)])\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestAwesome(self, s: str) -> int:\n",
    "        ref = defaultdict(lambda : [inf, -inf])\n",
    "        p = 0\n",
    "        for i in range(len(s)):\n",
    "            p ^= 1 << int(s[i])\n",
    "            ref[p][0] = min(ref[p][0], i)\n",
    "            ref[p][1] = max(ref[p][1], i)\n",
    "        ans = 0\n",
    "        for i in range(1 << 10):\n",
    "            if ref[i][0] != inf:\n",
    "                ans = max(ans, ref[i][1] - ref[i][0] + 1)\n",
    "                for j in range(10):\n",
    "                    if ref[i ^ (1 << j)][0] != inf:\n",
    "                        ans = max(ans, ref[i ^ (1 << j)][1] - ref[i][0])\n",
    "        ans = max(ans, ref[0][1] + 1)\n",
    "        for i in range(10):\n",
    "            ans = max(ans, ref[1 << i][1] + 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestAwesome(self, s: str) -> int:\n",
    "        ans = cur = 0\n",
    "        pre = {0:-1}\n",
    "        for i, j in enumerate(map(int, s)):\n",
    "            cur ^= 1 << j\n",
    "            for k in range(11):\n",
    "                maybe = (cur ^ 1 << k) & 1023\n",
    "                if maybe in pre and i - pre[maybe] > ans:\n",
    "                    ans = i - pre[maybe]\n",
    "            if cur not in pre: pre[cur] = i\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestAwesome(self, s: str) -> int:\n",
    "        seq = ans = 0\n",
    "        prefix_m = {0:-1}\n",
    "        for i,x in enumerate(s):\n",
    "            t = ord(x) - ord('0')\n",
    "            seq ^= (1 << t) # 奇偶变换\n",
    "            if seq in prefix_m:\n",
    "                ans = max(ans,i - prefix_m[seq]) # 同奇或同偶,说明区间[j + 1,i]内元素个数都为偶数\n",
    "            else:\n",
    "                prefix_m[seq] = i\n",
    "            for k in range(10):\n",
    "                if seq ^ (1 << k) in prefix_m: # 说明区间内有一个元素个数为奇数\n",
    "                    ans = max(ans,i - prefix_m[seq^(1 << k)])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestAwesome(self, s: str) -> int:\n",
    "\n",
    "        cnt = {0: -1}\n",
    "        cur = 0\n",
    "        ans = 1\n",
    "        for i, ch in enumerate(s):\n",
    "            cur ^= 1 << int(ch)\n",
    "            if not cur:\n",
    "                ans = i + 1\n",
    "            else:\n",
    "                for j in range(10):\n",
    "                    if cur ^ 1 << j in cnt:\n",
    "                        ans = max(ans, i - cnt[cur ^ 1 << j])\n",
    "            if cur not in cnt:\n",
    "                cnt[cur] = i\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestAwesome(self, s: str) -> int:\n",
    "        presum=0\n",
    "        dic={0:-1}\n",
    "        ans=1\n",
    "        for i,x in enumerate(s):\n",
    "            presum^=(1<<(int(x)))\n",
    "            for c in range(10):\n",
    "                cur=presum ^(1 << c)\n",
    "                if cur in dic:\n",
    "                    ans=max(ans,i-dic[cur])\n",
    "            if presum in dic:\n",
    "                ans=max(ans,i-dic[presum])\n",
    "            else:\n",
    "                dic[presum]=i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestAwesome(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        mp = defaultdict(int)\n",
    "        mp[0] = -1\n",
    "        cur = 0\n",
    "        ans = 1\n",
    "        for i,c in enumerate(s):\n",
    "            c = int(c)\n",
    "            cur ^= (1<<c)\n",
    "            print(i,bin(cur)[2:])\n",
    "            if cur in mp.keys():\n",
    "                if cur == 0 and i==n-1:\n",
    "                    ans = max(ans,i-mp[cur])\n",
    "                else:\n",
    "                    ans = max(ans,i-mp[cur]+1)\n",
    "            else:\n",
    "                mp[cur] = i\n",
    "            # 判断再带一个的情况\n",
    "            curr = cur\n",
    "            for j in range(10):\n",
    "                curr ^= (1<<j)\n",
    "                if i == 8:\n",
    "                    print(10,curr)\n",
    "                if curr in mp.keys():\n",
    "                    ans = max(ans, i-mp[curr])\n",
    "                curr ^= (1<<j)\n",
    "                \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestAwesome(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        mp = defaultdict(int)\n",
    "        mp[0] = -1\n",
    "        cur = 0\n",
    "        ans = 1\n",
    "        for i,c in enumerate(s):\n",
    "            c = int(c)\n",
    "            cur ^= (1<<c)\n",
    "            print(i,bin(cur)[2:])\n",
    "            if cur in mp.keys():\n",
    "                if cur == 0 and i==n-1:\n",
    "                    ans = max(ans,i-mp[cur])\n",
    "                else:\n",
    "                    ans = max(ans,i-mp[cur]+1)\n",
    "            else:\n",
    "                mp[cur] = i\n",
    "            # 判断再带一个的情况\n",
    "    \n",
    "            for j in range(10):\n",
    "                curr = cur ^(1<<j)\n",
    "                if curr in mp.keys():\n",
    "                    ans = max(ans, i-mp[curr])\n",
    "   \n",
    "                \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestAwesome(self, s: str) -> int:\n",
    "        get_n = lambda x: ord(x) - ord('0')\n",
    "        P = [0]\n",
    "        ans = 0\n",
    "        for ch in s:\n",
    "            P.append(P[-1] ^ (1<<get_n(ch)))\n",
    "        n = len(s)\n",
    "        aux = {}\n",
    "        aux[0] = 0\n",
    "        for r in range(n):\n",
    "            if P[r+1] in aux:\n",
    "                ans = max(ans, r+1-aux[P[r+1]])\n",
    "            for k in range(10):\n",
    "                if P[r+1] ^ (1<<k) in aux:\n",
    "                    ans = max(ans, r+1-aux[P[r+1]^(1<<k)])\n",
    "            if P[r+1] not in aux:\n",
    "                aux[P[r+1]] = r+1\n",
    "        return ans\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestAwesome(self, s: str) -> int:\n",
    "        # 有限次交换后可变成回文字符串 -- 正序和逆序相同就是回文\n",
    "        # 即如果子字符串长度为偶数:则其中元素每个必然出现偶数次;如果是奇数,必然有一个元素出现奇数次,其余均出现偶数次\n",
    "        # 字符串仅包含数字 -- 返回最长的\n",
    "        s = [1<<int(i) for i in s]\n",
    "        accu = list(accumulate(s,xor,initial=0))\n",
    "        n = len(s)\n",
    "        mp = dict()\n",
    "        res = 0\n",
    "        for i in range(n+1):\n",
    "            #if accu[i] in mp and (i-mp[accu[i]])%2==0:\n",
    "            if accu[i] in mp:\n",
    "                res = max(res,i-mp[accu[i]])\n",
    "            for k in range(10):\n",
    "                tmp = accu[i]^(1<<k)\n",
    "                #if tmp in mp and (i-mp[tmp])%2 == 1:\n",
    "                if tmp in mp:\n",
    "                    res = max(res,i-mp[tmp])\n",
    "            if accu[i] not in mp:\n",
    "                mp[accu[i]] = i\n",
    "        return res\n",
    "                    \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
